﻿using Pagination.RangeCollector;

namespace Pagination.Storage
{
    internal class ListNode
    {
        public readonly int Element;
        public ListNode Next;

        public ListNode(int element = default(int), ListNode next = null)
        {
            Element = element;
            Next = next;
        }
    }

    internal class Lane
    {
        public readonly Lane Down;
        public readonly ListNode Node;
        public Lane Right;
        public int Width;

        public Lane(ListNode node, Lane down = null, Lane right = null, int width = 1)
        {
            Node = node;
            Down = down;
            Right = right;
            Width = width;
        }
    }

    public class TwoDimensionallyLinkedSkipList : IStorage
    {
        private const int MaxLevel = 32;
        private readonly IRangeCollector collector;
        private readonly Lane[] lanes = new Lane[MaxLevel + 1];
        private readonly ILevelProvider levelProvider;
        private readonly int[] steps = new int[MaxLevel + 1];
        private readonly Lane[] update = new Lane[MaxLevel + 1];
        private Lane headLane = new Lane(new ListNode());
        private int level = 1;

        public TwoDimensionallyLinkedSkipList(IRangeCollector collector, ILevelProvider levelProvider)
        {
            this.collector = collector;
            this.levelProvider = levelProvider;
        }

        #region IStorage Members

        public void Add(int element)
        {
            var predecessor = BuildUpdateTableAndStepsReturnPrecessor(element);
            var newNode = new ListNode(element, predecessor.Next);
            predecessor.Next = newNode;
            var newLevel = levelProvider.NewLevel(MaxLevel);
            if (newLevel > level)
            {
                newLevel = level + 1;
                headLane = update[newLevel] = new Lane(headLane.Node, headLane);
                level = newLevel;
            }
            lanes[0] = null;
            AddLane(newLevel, newNode);
        }

        public void Range(int from, int to)
        {
            var rangeLength = to - from + 1;
            var index = from;
            var lane = headLane;
            for (var currentLevel = level; currentLevel > 0; --currentLevel)
            {
                while (lane.Right != null && lane.Width <= index)
                {
                    index -= lane.Width;
                    lane = lane.Right;
                }
                if (currentLevel > 1)
                    lane = lane.Down;
            }
            var node = lane.Node;
            while (node.Next != null && index != 0)
            {
                --index;
                node = node.Next;
            }
            for (var idx = 0; idx < rangeLength; ++idx)
            {
                collector.Append(node.Element);
                node = node.Next;
            }
            collector.End();
        }

        #endregion

        private ListNode BuildUpdateTableAndStepsReturnPrecessor(int element)
        {
            var lane = headLane;
            for (var currentLevel = level; currentLevel > 0; --currentLevel)
            {
                steps[currentLevel] = 0;
                while (lane.Right != null && lane.Right.Node.Element <= element)
                {
                    steps[currentLevel] += lane.Width;
                    lane = lane.Right;
                }
                update[currentLevel] = lane;
                lane = lane.Down;
            }
            var node = update[1].Node;
            steps[0] = 0;
            while (node.Next != null && node.Next.Element <= element)
            {
                ++steps[0];
                node = node.Next;
            }
            return node;
        }

        private void AddLane(int laneLevel, ListNode newNode)
        {
            var currentSteps = steps[0];
            for (var currentLevel = 1; currentLevel <= laneLevel; ++currentLevel)
            {
                var updateLane = update[currentLevel];
                lanes[currentLevel] = new Lane(newNode, lanes[currentLevel - 1], updateLane.Right,
                                               updateLane.Width - currentSteps);
                updateLane.Right = lanes[currentLevel];
                updateLane.Width = currentSteps + 1;
                currentSteps += steps[currentLevel];
            }
            for (var currentLevel = laneLevel + 1; currentLevel <= level; ++currentLevel)
                ++update[currentLevel].Width;
        }
    }
}